package club.xiaojiawei.dp;

import java.util.HashSet;
import java.util.Set;

/**
 * @author 肖嘉威
 * @version 1.0
 * @date 6/7/22 9:05 PM
 * @question 718. 最长重复子数组
 * @description 给两个整数数组 nums1 和 nums2 ，返回 两个数组中 公共的 、长度最长的子数组的长度 。
 */
public class FindLength718 {

    public static void main(String[] args) {
        FindLength718 test = new FindLength718();
        int result = test.findLength(new int[]{1, 2, 3, 2, 1}, new int[]{3, 2, 1, 4, 7});
        System.out.println(result);
    }

    /**
     * 官方-dp
     * 时间复杂度 O(m*n)
     * 空间复杂度 O(m*n)
     * @param A
     * @param B
     * @return
     */
    public int findLength(int[] A, int[] B) {
        int n = A.length, m = B.length;
        int[][] dp = new int[n + 1][m + 1];
        int ans = 0;
        for (int i = n - 1; i >= 0; i--) {
            for (int j = m - 1; j >= 0; j--) {
                dp[i][j] = A[i] == B[j] ? dp[i + 1][j + 1] + 1 : 0;
                ans = Math.max(ans, dp[i][j]);
            }
        }
        return ans;
    }

    /**
     * 官方-滑动窗口
     * 时间复杂度 O((m+n)*min(m,n))
     * 空间复杂度 O(1)
     * @param A
     * @param B
     * @return
     */
    public int findLength2(int[] A, int[] B) {
        int n = A.length, m = B.length;
        int ret = 0;
//        下面两个for循环是遍历所有对齐方式，然后在每一种对齐方式下寻找最长相同子数组
//        移动B数组对齐A数组
        for (int i = 0; i < n; i++) {
            int len = Math.min(m, n - i);
            if(len <= ret){
                break;
            }
            int maxLen = maxLength(A, B, i, 0, len);
            ret = Math.max(ret, maxLen);
        }
//        移动A数组对齐B数组
        for (int i = 0; i < m; i++) {
            int len = Math.min(n, m - i);
            if(len <= ret){
                break;
            }
            int maxLen = maxLength(A, B, 0, i, len);
            ret = Math.max(ret, maxLen);
        }
        return ret;
    }

    public int maxLength(int[] A, int[] B, int addA, int addB, int len) {
        int ret = 0, k = 0;
        for (int i = 0; i < len; i++) {
            if (A[addA + i] == B[addB + i]) {
                k++;
            } else {
                k = 0;
            }
            ret = Math.max(ret, k);
        }
        return ret;
    }

    /**
     * 官方-二分查找+哈希
     * @param A
     * @param B
     * @return
     */
    public int findLength3(int[] A, int[] B) {
        int left = 1, right = Math.min(A.length, B.length) + 1;
        while (left < right) {
            int mid = (left + right) >> 1;
            if (check(A, B, mid)) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left - 1;
    }

    int mod = 1000000009;
    int base = 113;

    public boolean check(int[] A, int[] B, int len) {
        long hashA = 0;
        for (int i = 0; i < len; i++) {
            hashA = (hashA * base + A[i]) % mod;
        }
        Set<Long> bucketA = new HashSet<Long>();
        bucketA.add(hashA);
        long mult = qPow(base, len - 1);
        for (int i = len; i < A.length; i++) {
            hashA = ((hashA - A[i - len] * mult % mod + mod) % mod * base + A[i]) % mod;
            bucketA.add(hashA);
        }
        long hashB = 0;
        for (int i = 0; i < len; i++) {
            hashB = (hashB * base + B[i]) % mod;
        }
        if (bucketA.contains(hashB)) {
            return true;
        }
        for (int i = len; i < B.length; i++) {
            hashB = ((hashB - B[i - len] * mult % mod + mod) % mod * base + B[i]) % mod;
            if (bucketA.contains(hashB)) {
                return true;
            }
        }
        return false;
    }

    // 使用快速幂计算 x^n % mod 的值
    public long qPow(long x, long n) {
        long ret = 1;
        while (n != 0) {
            if ((n & 1) != 0) {
                ret = ret * x % mod;
            }
            x = x * x % mod;
            n >>= 1;
        }
        return ret;
    }

    /**
     * 民间-二分查找+哈希
     * @param nums1
     * @param nums2
     * @return
     */
    public int findLength4(int[] nums1, int[] nums2) {
        int n = nums1.length, m = nums2.length;
        hashA = new int[n + 1];
        hashB = new int[m + 1];
        p = new int[Math.max(n, m) + 1];

        // 预处理出所有的哈希值
        p[0] = 1; // P^0 = 1
        for (int i = 1; i < p.length; i++) {
            p[i] = p[i - 1] * P;
        }

        for (int i = 1; i <= n; i++) {
            hashA[i] = hashA[i - 1] * P + nums1[i - 1];
        }

        for (int i = 1; i <= m; i++) {
            hashB[i] = hashB[i - 1] * P + nums2[i - 1];
        }

        // 开始二分
        int l = 0, r = Math.min(n, m);
        while (l < r) {
            int mid = l + r + 1 >> 1; // 查看一下这个长度是否存在公共子数组
            if (check(mid)) l = mid; // 若这个长度存在, 则答案在右侧
            else r = mid - 1;
        }
        return l;
    }
    final int P = 131;
    int[] hashA, hashB;
    int[] p; // 存P的幂

    // 检查@len 这个长度, 是否存在公共子数组
    private boolean check(int len) {
        Set<Integer> set = new HashSet<>();
        int n = hashA.length - 1;
        int m = hashB.length - 1;
        for (int i = 1; i + len - 1 <= n; i++) {
            int h = hashA[i + len - 1] - hashA[i - 1] * p[len];
            set.add(h);
        }

        for (int i = 1; i + len - 1 <= m; i++) {
            int h = hashB[i + len - 1] - hashB[i - 1] * p[len];
            if (set.contains(h)) return true;
        }
        return false;
    }

    /**
     * 民间-滑动窗口-简化
     * @param A
     * @param B
     * @return
     */
    public int findLength5(int[] A, int[] B) {
        int m = A.length, n = B.length, res = 0;
        for(int diff = -(m - 1); diff <= n - 1; ++diff) { // 枚举对应关系
            for(int i = Math.max(0, -diff), l = 0; i < Math.min(m, n - diff); ++i) { // 遍历公共部分
                l = (A[i] == B[i + diff])? (l + 1) : 0;
                res = Math.max(res, l);
            }
        }
        return res;
    }
}
